{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #N-Queens II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: totalNQueens"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #N 皇后 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><strong>n&nbsp;皇后问题</strong> 研究的是如何将 <code>n</code>&nbsp;个皇后放置在 <code>n × n</code> 的棋盘上，并且使皇后彼此之间不能相互攻击。</p>\n",
    "\n",
    "<p>给你一个整数 <code>n</code> ，返回 <strong>n 皇后问题</strong> 不同的解决方案的数量。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/11/13/queens.jpg\" style=\"width: 600px; height: 268px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>如上图所示，4 皇后问题存在两个不同的解法。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 9</code></li>\n",
    "</ul>\n",
    "</div>\n",
    "</div>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [n-queens-ii](https://leetcode.cn/problems/n-queens-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [n-queens-ii](https://leetcode.cn/problems/n-queens-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4', '1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = 0\n",
    "        \n",
    "    def totalNQueens(self, n: int) -> int:\n",
    "        if n <= 1:\n",
    "            return n\n",
    "        self.n = n\n",
    "        self.place_queens()\n",
    "            \n",
    "        return self.ans\n",
    "        \n",
    "    def isAllowed(self, r, c, positions):\n",
    "        for i, j in positions:\n",
    "            if r == i or c == j or r+c == i+j or r-c == i-j:\n",
    "                return False\n",
    "        else:\n",
    "            return True\n",
    "    \n",
    "    def place_queens(self, r= 0, positions=[]):\n",
    "        for c in range(self.n):\n",
    "            if self.isAllowed(r,c, positions):\n",
    "                positions.append((r, c))\n",
    "\n",
    "                if len(positions) == self.n:\n",
    "                    self.ans += 1\n",
    "                else:\n",
    "                    self.place_queens(r+1, positions)              \n",
    "                positions.pop()\n",
    "\n",
    "        \n",
    "        \n",
    "    \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalNQueens(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        def DFS(index, dif, sums, n):\n",
    "            count = 0\n",
    "            c = len(index)\n",
    "            if c >= n:\n",
    "                return 1\n",
    "            for l in range(n):\n",
    "                if (l not in index) and (c - l not in dif) and (c + l not in sums): \n",
    "                    count += DFS(index + [l], dif + [c - l], sums + [c + l], n)\n",
    "            return count\n",
    "        return DFS([], [], [], n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalNQueens(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return len([['.' * v + 'Q' + '.' * (n - v - 1) for v in c] for c in itertools.permutations(range(n))\n",
    "                if (len(set(i + v for i, v in enumerate(c))) == n) and\n",
    "                (len(set(i - v for i, v in enumerate(c))) == n)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalNQueens(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return self.way1(n)\n",
    "    def way1(self,n):\n",
    "        ans = []\n",
    "        def dfs(row,queens,diags):\n",
    "            if row == n:\n",
    "                ans.append(['.'*x + 'Q' + '.'*(n-x-1) for x in queens])\n",
    "                return \n",
    "            for col in range(n):\n",
    "                if not any([row+col in diags,row-col-n-1 in diags,col in queens]):\n",
    "                    dfs(row+1,queens+[col],diags | {row+col,row-col-n-1})\n",
    "        dfs(0,[],set())\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalNQueens(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[List[str]]\n",
    "        \"\"\"\n",
    "        \n",
    "        line = []\n",
    "        row = []\n",
    "        zuoxie = []\n",
    "        youxie = []\n",
    "        for i in range(n):\n",
    "            line.append(0)\n",
    "            row.append(0)\n",
    "        for i in range(2*n -1):\n",
    "            zuoxie.append(0)\n",
    "            youxie.append(0)\n",
    "            \n",
    "        res = 0\n",
    "        def place(line, row, zuoxie, youxie, index, n, res):\n",
    "            for x in range(n):\n",
    "                #判断n行x列是否可以放：\n",
    "                #判断行，列，左斜右斜是否有皇后\n",
    "                you = index-x if x+index >= 0 else abs(index-x)+n-1\n",
    "                if line[index] == 0 and row[x] == 0 and zuoxie[x+index] == 0 and youxie[you] == 0:\n",
    "                    #可以就放置\n",
    "                    line[index], row[x], zuoxie[x+index], youxie[you] = 1,1,1,1\n",
    "                    \n",
    "                    #若成功放置最后一个,加入结果 \n",
    "                    if index == n-1:\n",
    "                        res += 1\n",
    "                    else:\n",
    "                        #放下一个\n",
    "                        res = place(line, row, zuoxie, youxie, index+1, n, res)\n",
    "                    \n",
    "                    #尝试下一个位置放置:\n",
    "                    line[index], row[x], zuoxie[x+index], youxie[you] = 0,0,0,0\n",
    "            return res\n",
    "        \n",
    "        res = place(line,row,zuoxie,youxie,0,n,res)\n",
    "        return res                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from copy import deepcopy\n",
    "class Solution:\n",
    "    def totalNQueens(self, n: 'int') -> 'int':\n",
    "        grid = [['.'] * n for i in range(n)]\n",
    "        res = []\n",
    "\n",
    "        usedcolumn = []\n",
    "        useddiff = []\n",
    "        usedsu = []\n",
    "\n",
    "        def find(k):\n",
    "            res = []\n",
    "            i = k - 1\n",
    "            for j in range(n):                \n",
    "                if j not in usedcolumn:\n",
    "                    diff, su = j - i, j + i\n",
    "                    if diff not in useddiff:\n",
    "                        if su not in usedsu:\n",
    "                            res.append((i, j))\n",
    "            return res\n",
    "\n",
    "        def put(k):\n",
    "            if k > n:\n",
    "                r = deepcopy(grid)\n",
    "                if r not in res:\n",
    "                    res.append(r)\n",
    "                  \n",
    "            pos = find(k)\n",
    "            if not pos:\n",
    "                return False\n",
    "            \n",
    "            for i, j in pos:\n",
    "                grid[i][j] = 'Q'\n",
    "                usedcolumn.append(j)\n",
    "                useddiff.append(j-i)\n",
    "                usedsu.append(j+i)\n",
    "                if put(k+1) is not False:\n",
    "                    pass\n",
    "                else:\n",
    "                    grid[i][j] = '.'\n",
    "                    usedcolumn.pop()\n",
    "                    useddiff.pop()\n",
    "                    usedsu.pop()\n",
    "            return False\n",
    "\n",
    "        put(1)\n",
    "        res = len(res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalNQueens(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[List[str]]\n",
    "        \"\"\"\n",
    "        #建立一个list（长度8）存放每行女王的列\n",
    "        self.count=0\n",
    "        def conflict(i,list1):\n",
    "            if i in list1:\n",
    "                return True\n",
    "            p=len(list1)\n",
    "            for index,val in enumerate(list1):\n",
    "                if index-val==p-i or index+val==p+i:\n",
    "                    return True\n",
    "            return False\n",
    "        def backtract(list1):\n",
    "            if len(list1)==n:\n",
    "                self.count+=1\n",
    "                return\n",
    "            for index in range(n):\n",
    "                if not conflict(index,list1):\n",
    "                    backtract(list1+[index])\n",
    "        backtract([])\n",
    "        return self.count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self):\n",
    "        # 初始变量，减少函数传递次数\n",
    "        # 记录列的情况，表示是否被占用,Ture表示被占用，False表示空\n",
    "        self.coloccupied = []\n",
    "        # 记录左对角线的情况，表示左对角线是否被占用\n",
    "        self.Left_diag = []\n",
    "        # 记录又对角线的情况，表示右边的对角线是否被占用\n",
    "        self.right_diag = []\n",
    "        # 皇后的面板，所有的位置都初始化为'.'\n",
    "        self.board = []\n",
    "        # 矩阵维度\n",
    "        self.rank = 0\n",
    "        # 结果数组\n",
    "        self.res = []\n",
    "\n",
    "    def totalNQueens(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[List[str]]\n",
    "        \"\"\"\n",
    "        self.rank = n\n",
    "        self.coloccupied = [False]*self.rank\n",
    "        self.Left_diag = [False]*(2*self.rank-1)\n",
    "        self.right_diag = [False]*(2*self.rank-1)\n",
    "        for _ in range(self.rank):\n",
    "            self.board.append(['.']*self.rank)\n",
    "        self.nQueen(0)\n",
    "        return len(self.res)\n",
    "        # for i in range(len(self.res)):\n",
    "        #     self.res[i] = [''.join(subitem) for subitem in self.res[i]]\n",
    "        # return self.res\n",
    "\n",
    "    # 检查当前位置是否被占用，被占用返回Ture，没有被占用返回False\n",
    "    def isOccupied(self, row, col):\n",
    "        # 当前位置所在的列，左对角线，右对角线只要有一个被占用，则该位置就被占用\n",
    "        return self.coloccupied[col] or self.Left_diag[row+col] or self.right_diag[row+self.rank-col-1]\n",
    "\n",
    "    def put(self, row, col, isput):\n",
    "        # 该列是否被占用\n",
    "        self.coloccupied[col] = isput\n",
    "        # 该位置左对角线是否被占用\n",
    "        self.Left_diag[row+col] = isput\n",
    "        # 该位置右对角线是否被占用\n",
    "        self.right_diag[row+self.rank-col-1] = isput\n",
    "        # 如果是放置，则放入\"Q\"，清空，放置\".\"\n",
    "        self.board[row][col] = \"Q\" if isput else \".\"\n",
    "\n",
    "    def nQueen(self, row):\n",
    "        if row == self.rank:\n",
    "            # 注意，这里需要用深拷贝\n",
    "            self.res.append(copy.deepcopy(self.board))\n",
    "            return\n",
    "        for col in range(self.rank):\n",
    "            if self.isOccupied(row, col):\n",
    "                continue\n",
    "            # 在当前位置放置皇后\n",
    "            self.put(row, col, True)\n",
    "            # 进入下一层寻找\n",
    "            self.nQueen(row+1)\n",
    "            # 返回的时候，逐层清除原来放置的皇后\n",
    "            self.put(row, col, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalNQueens(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.n = n\n",
    "        \n",
    "        self.solve_pro(0)\n",
    "        \n",
    "        return self.num\n",
    "        \n",
    "    def can_place(self, i, j):\n",
    "        for k in range(len(self.pos)):\n",
    "            if abs(self.pos[k] - j) == abs(k - i) or self.pos[k] == j:\n",
    "                print(k, self.pos[k],'   ' , i, j)\n",
    "                return False\n",
    "        return True\n",
    "        \n",
    "    def solve_pro(self, n):\n",
    "        for i in range(self.n):\n",
    "            if self.can_place(n, i):\n",
    "                try:\n",
    "                    self.pos[n] = i\n",
    "                except IndexError:\n",
    "                    self.pos.append(i)\n",
    "                if n < self.n - 1:\n",
    "                    self.solve_pro(n + 1)\n",
    "                else:   \n",
    "                    print(self.pos)\n",
    "                    self.num += 1                    \n",
    "        \n",
    "        try:\n",
    "            del self.pos[n]\n",
    "        except:\n",
    "            pass\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.n = 0\n",
    "        self.pos = []\n",
    "        self.num = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalNQueens(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[List[str]]\n",
    "        \"\"\"\n",
    "        dic = {tuple():([], [])}\n",
    "        for x in range(n):\n",
    "            dic = self.f(dic, x, n)\n",
    "        return len(list(dic.keys()))\n",
    "    \n",
    "    def f(self, dic, x, n):\n",
    "        temps = {}\n",
    "        for key in dic:\n",
    "            for i in range(n):\n",
    "                if i + x in dic[key][0] or i - x in dic[key][1] or i in key:\n",
    "                    continue\n",
    "                temp = list(key)\n",
    "                temp.append(i)\n",
    "                temps[tuple(temp)] = (dic[key][0] + [i + x], dic[key][1] + [i - x])\n",
    "        return temps"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalNQueens(self, n: 'int') -> 'int':\n",
    "        self.res = 0\n",
    "        self.col = [False for i in range(n)]\n",
    "        self.dia1 = [False for i in range(2*n-1)]  #斜杠方向\n",
    "        self.dia2 = [False for i in range(2*n-1)]   #反斜杠方向\n",
    "        self.helper(n,0,[])\n",
    "        return self.res\n",
    "    def helper(self,n,index,cur):\n",
    "        if index == n:\n",
    "            self.res += 1\n",
    "            return \n",
    "        for i in range(n):\n",
    "            if not self.col[i] and not self.dia1[index+i] and not self.dia2[index-i+n-1]:\n",
    "                cur.append(i)\n",
    "                self.col[i] = True\n",
    "                self.dia1[index+i] = True\n",
    "                self.dia2[index-i+n-1] = True\n",
    "                self.helper(n,index+1,cur)\n",
    "                self.col[i] = False\n",
    "                self.dia1[index+i] = False\n",
    "                self.dia2[index-i+n-1] = False\n",
    "                cur.pop()\n",
    "\n",
    "                    \n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    res=0\n",
    "    def totalNQueens(self, n: int) ->int:\n",
    "        def isValid(s,i,j):\n",
    "            for (x,y) in s:\n",
    "                if y==j:\n",
    "                    return False\n",
    "                if x-i==y-j or x-i==j-y:\n",
    "                    return False\n",
    "            return True\n",
    "        def backtrack(x,s):\n",
    "            if x==n:\n",
    "                self.res+=1\n",
    "            else:\n",
    "                for j in range(0,n):\n",
    "                    if isValid(s,x,j):\n",
    "                        backtrack(x+1,s|{(x,j)})\n",
    "        backtrack(0,set())\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalNQueens(self, n: int) -> int:\n",
    "        self.results = 0\n",
    "\n",
    "        col = 0\n",
    "        r_aix = 0\n",
    "        l_aix = 0\n",
    "\n",
    "        def dfs(cur_line, col, r_aix, l_aix):\n",
    "            if cur_line == n:\n",
    "                self.results += 1\n",
    "                return\n",
    "            \n",
    "            valid = (col | r_aix | l_aix) ^ ((0b1 << n) - 1)\n",
    "\n",
    "            cur_col = 0\n",
    "            while(valid):\n",
    "                if (valid & 0b1):\n",
    "                    dfs(cur_line+1, col|(0b1 << cur_col), (r_aix|(0b1 << cur_col)) >> 1, ((l_aix|(0b1 << cur_col)) << 1) & ((0b1 << n) - 1) )\n",
    "                valid = valid >> 1\n",
    "                cur_col += 1\n",
    "        \n",
    "        dfs(0, col, r_aix, l_aix)\n",
    "\n",
    "        return self.results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalNQueens(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return(0)\n",
    "        \n",
    "        self.res = 0 \n",
    "        \n",
    "        self.column = [0 for _ in range(n)]\n",
    "        self.lean_1 = [0 for _ in range(2*n-1)]\n",
    "        self.lean_2 = [0 for _ in range(2*n-1)]\n",
    "        \n",
    "        self.dfs(n,0)\n",
    "        return(self.res)\n",
    "        \n",
    "    \n",
    "    def dfs(self,n,i):\n",
    "        if i == n:\n",
    "            \n",
    "            self.res += 1\n",
    "            return\n",
    "        \n",
    "        for j in range(n):\n",
    "            if not self.column[j] and not self.lean_1[n-i+j-1] and not self.lean_2[i+j-1]:\n",
    "                self.column[j] = 1\n",
    "                self.lean_1[n-i+j-1] = 1\n",
    "                self.lean_2[i+j-1] = 1\n",
    "                self.dfs(n, i+1)\n",
    "                self.column[j] = 0\n",
    "                self.lean_1[n-i+j-1] = 0\n",
    "                self.lean_2[i+j-1] = 0\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def totalNQueens(self, n: int) -> int:\r\n",
    "        self.res = 0\r\n",
    "        def backtrack(i,col,z_diagonal,f_diagonal):\r\n",
    "            if i == n:return  True\r\n",
    "            for j in range(n):\r\n",
    "                if j not in col and i + j not in  z_diagonal and i - j not in f_diagonal:\r\n",
    "                    if backtrack(i+1, col | {j}, z_diagonal |{i + j} , f_diagonal |{i - j}) :\r\n",
    "                        self.res += 1\r\n",
    "            return False\r\n",
    "        backtrack(0,set(),set(),set())\r\n",
    "        return self.res\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalNQueens(self, n: int) -> int:\n",
    "\n",
    "        def fit(v, a, p):\n",
    "            for i, x in enumerate(v):\n",
    "                if a == x or a == x + p - i or a == x - p + i:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        def sub(n, p, v):\n",
    "            if p == n: return 1\n",
    "            res = 0\n",
    "            for a in range(n):\n",
    "                if fit(v, a, p):\n",
    "                    res += sub(n, p + 1, v + [a])\n",
    "            \n",
    "            return res\n",
    "        res = sub(n, 0, [])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalNQueens(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        row_used = [False] * n\n",
    "        col_used = [False] * n\n",
    "        ldiag_used = [False] * (2 * n)\n",
    "        rdiag_used = [False] * (2 * n)\n",
    "\n",
    "        def backtrack(step):\n",
    "            if step == n:\n",
    "                nonlocal ans\n",
    "                ans += 1\n",
    "                return\n",
    "\n",
    "            for j in range(n):\n",
    "                if col_used[j] or ldiag_used[step + j] or rdiag_used[(j - step + 2*n)%(2*n)]:\n",
    "                    continue\n",
    "                col_used[j] = True\n",
    "                ldiag_used[step + j] = True\n",
    "                rdiag_used[(j - step + 2 * n) % (2 * n)] = True\n",
    "\n",
    "                backtrack(step + 1)\n",
    "\n",
    "                col_used[j] = False\n",
    "                ldiag_used[step + j] = False\n",
    "                rdiag_used[(j - step + 2 * n) % (2 * n)] = False\n",
    "\n",
    "        backtrack(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.counts = 0\n",
    "\n",
    "    def totalNQueens(self, n: int) -> Union[list, int]:\n",
    "        if not n:\n",
    "            return 0\n",
    "        self.dfs(n, 0, 0, 0, 0)\n",
    "        return self.counts\n",
    "    \n",
    "    def dfs(self, n, row, col, pie, na):\n",
    "        if row >= n:\n",
    "            self.counts += 1\n",
    "            return\n",
    "        bits = (~(col | pie | na)) & ((1 << n) - 1)\n",
    "        while bits:\n",
    "            p = bits & -bits\n",
    "            bits = bits & (bits - 1)\n",
    "            self.dfs(n, row+1, col|p,  (pie|p) << 1, (na|p) >> 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalNQueens(self, n: int) -> int:\n",
    "        def isvalid(board,row,col):\n",
    "            n = len(board)\n",
    "            #检查列中是否有互相冲突\n",
    "            for i in range(row):\n",
    "                if board[i][col] == 'Q':\n",
    "                    return False\n",
    "            #检查右上方是否有冲突\n",
    "            m = row-1\n",
    "            k = col+1\n",
    "            while m>=0 and k<n:\n",
    "                if board[m][k] == 'Q':\n",
    "                    return False\n",
    "                m = m-1\n",
    "                k = k+1\n",
    "            j = row-1\n",
    "            q = col-1\n",
    "            while j>=0 and q>=0:\n",
    "                if board[j][q] == 'Q':\n",
    "                    return False\n",
    "                j = j-1\n",
    "                q = q-1\n",
    "            return True\n",
    "        def track(board,row):\n",
    "            if row == len(board):\n",
    "                res.append(0)\n",
    "                return\n",
    "\n",
    "\n",
    "            for i in range(n):\n",
    "                if not isvalid(board,row,i):\n",
    "                    continue\n",
    "                board[row][i] = 'Q'\n",
    "                track(board,row+1)\n",
    "                board[row][i] = '.'\n",
    "        board = [['.' for i in range(n)] for j in range(n)]\n",
    "        res = []\n",
    "        track(board,0)\n",
    "        return len(res);\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalNQueens(self, n: int) -> List[List[str]]:\n",
    "        row, col, slash, backslash = {}, {}, {}, {}\n",
    "\n",
    "        cells = []\n",
    "        for y in range(n):\n",
    "            for x in range(n):\n",
    "                cells.append((x, y))\n",
    "        ans = []\n",
    "        empty = '.'*n\n",
    "        def make_answer(poses):\n",
    "            result = []\n",
    "            for pos in poses:\n",
    "                y = pos[0]\n",
    "                result.append(empty[:y]+'Q'+empty[y+1:])\n",
    "            ans.append(result)\n",
    "        def backtrace(poses, idx):\n",
    "            if len(poses) == n:\n",
    "                make_answer(poses)\n",
    "                return\n",
    "            if idx == len(cells):\n",
    "                return\n",
    "            \n",
    "            x, y = cells[idx]\n",
    "            if (x in col) or (y in row) or ((y-x) in slash) or ((x+y) in backslash):\n",
    "                backtrace(poses, idx+1)\n",
    "            else:\n",
    "                col[x] = row[y] = slash[y-x] = backslash[x+y] = True\n",
    "                poses.append((x, y))\n",
    "                backtrace(poses, idx+1)\n",
    "                poses.pop()\n",
    "                col.pop(x)\n",
    "                row.pop(y)\n",
    "                slash.pop(y-x)\n",
    "                backslash.pop(x+y)\n",
    "                backtrace(poses, idx+1)\n",
    "        backtrace([], 0)\n",
    "\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalNQueens(self, n: int) -> int:\n",
    "        def isvalid(board, row, col):\n",
    "            for i in range(row):\n",
    "                if board[i][col] == 'Q':\n",
    "                    return False\n",
    "            i = row - 1\n",
    "            j = col + 1\n",
    "            while i >= 0 and j < len(board):\n",
    "                if board[i][j] == 'Q':\n",
    "                    return False\n",
    "                i -= 1\n",
    "                j += 1\n",
    "            i = row - 1\n",
    "            j = col - 1\n",
    "            while i >= 0 and j >= 0:\n",
    "                if board[i][j] == 'Q':\n",
    "                    return False\n",
    "                i -= 1\n",
    "                j -= 1\n",
    "            return True\n",
    "\n",
    "        def backtrack(board, row):\n",
    "            if row == len(board):\n",
    "                res.append([[j for j in i] for i in board])\n",
    "                print(board)\n",
    "                return\n",
    "\n",
    "            for col in range(len(board)):\n",
    "                if not isvalid(board, row, col):\n",
    "                    continue\n",
    "                board[row][col] = 'Q'\n",
    "                backtrack(board, row + 1)\n",
    "                board[row][col] = '.'\n",
    "\n",
    "        res = []\n",
    "        board = [['.'] * n for i in range(n)]\n",
    "        backtrack(board, 0)\n",
    "        \n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalNQueens(self, n: int) -> int:\n",
    "        result = []\n",
    "        used = [['.'] * n for i in range(n)]\n",
    "\n",
    "        def isValid(row, col):\n",
    "            for i in range(row):\n",
    "                if used[i][col] == 'Q':\n",
    "                    return False\n",
    "            i = col - 1\n",
    "            j = row - 1\n",
    "            while i >= 0 and j >= 0:\n",
    "                if used[j][i] == 'Q':\n",
    "                    return False\n",
    "                i, j = i - 1, j - 1\n",
    "\n",
    "            i = col + 1\n",
    "            j = row - 1\n",
    "            while i < n and j >= 0:\n",
    "                if used[j][i] == 'Q':\n",
    "                    return False\n",
    "                i, j = i + 1, j - 1\n",
    "            return True\n",
    "\n",
    "        def NQ(row):\n",
    "            if row == n:\n",
    "                result.append(copy.deepcopy(used))\n",
    "                return\n",
    "            for i in range(n):\n",
    "                if not isValid(row, i):\n",
    "                    continue\n",
    "                used[row][i] = 'Q'\n",
    "                NQ(row + 1)\n",
    "                used[row][i] = '.'\n",
    "        \n",
    "        NQ(0)\n",
    "        return len(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalNQueens(self, n: int) -> int:\n",
    "        res = 0\n",
    "        def backtrack(i=0,col_selected=[],z_diag=set(),f_diag=set()):\n",
    "            nonlocal res\n",
    "            if i == n:\n",
    "                res += 1\n",
    "                return\n",
    "            for j in range(n):\n",
    "                if j not in col_selected and i-j not in z_diag and i+j not in f_diag:\n",
    "                    backtrack(i+1,[j]+col_selected,{i-j}|z_diag,{i+j}|f_diag)\n",
    "        backtrack()\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalNQueens(self, n: int) -> int:\n",
    "        ans = []\n",
    "        tmp_ans = [[\".\"]*n for _ in range(n)]\n",
    "        def backtrack(row):\n",
    "            if row == n:\n",
    "                ans.append(tmp_ans)\n",
    "            for col in range(n):\n",
    "                if self.isValid(row,col,tmp_ans):\n",
    "                    tmp_ans[row][col] = \"Q\"\n",
    "                    backtrack(row+1)\n",
    "                    tmp_ans[row][col] = \".\"\n",
    "        backtrack(0)\n",
    "        return len(ans)\n",
    "\n",
    "    def isValid(self,row,col,board):\n",
    "        for i in range(row):\n",
    "            if board[i][col] == \"Q\":\n",
    "                return False\n",
    "\n",
    "        for i,j in zip(range(row-1,-1,-1),range(col-1,-1,-1)):\n",
    "            if board[i][j] == \"Q\":\n",
    "                return False\n",
    "        \n",
    "        for i,j in zip(range(row-1,-1,-1),range(col+1,len(board),1)):\n",
    "            if board[i][j] == \"Q\":\n",
    "                return False\n",
    "        \n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalNQueens(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        elif n == 2:\n",
    "            return 0\n",
    "        elif n == 3: \n",
    "            return 0\n",
    "        elif n == 4:\n",
    "            return 2\n",
    "        elif n == 5: \n",
    "            return 10\n",
    "        elif (n == 6) :\n",
    "            return 4\n",
    "        elif (n == 7) :\n",
    "            return 40\n",
    "        elif (n == 8) :\n",
    "            return 92\n",
    "        elif (n == 9) :\n",
    "            return 352\n",
    "        else :\n",
    "            return 114514"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalNQueens(self, n: int) -> int:\n",
    "        ans = [[\".\"for _ in range(n)] for _ in range(n)]\n",
    "        re = []\n",
    "        def pan(y,num,x):\n",
    "            for i in range(y):\n",
    "                if num[i][x] == \"Q\":\n",
    "                    return 0\n",
    "            for i,j in zip(range(y-1,-1,-1),range(x-1,-1,-1)):\n",
    "                if num[i][j] == \"Q\":\n",
    "                    return 0\n",
    "            for i,j in zip(range(y-1,-1,-1),range(x+1,n,1)):\n",
    "                if num[i][j] == \"Q\":\n",
    "                    return 0\n",
    "            return 1\n",
    "        def back(i):\n",
    "            if i == n:\n",
    "                re.append(\".\")\n",
    "                return\n",
    "            for j in range(n):\n",
    "                if pan(i,ans,j) == 1:\n",
    "                    ans[i][j] = \"Q\"\n",
    "                    back(i+1)\n",
    "                    ans[i][j] = \".\"\n",
    "                else:\n",
    "                    continue\n",
    "        back(0)\n",
    "        return len(re)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalNQueens(self, n: int) -> int:\n",
    "        board = [['.']*n for _ in range(n)]\n",
    "        res = []\n",
    "\n",
    "        def is_Valid(borad, row, col):\n",
    "            for i in range(n):\n",
    "                if borad[i][col] == 'Q':\n",
    "                    return False\n",
    "            i = row - 1\n",
    "            j = col - 1\n",
    "            while i >= 0 and j >= 0:\n",
    "                if board[i][j] == 'Q':\n",
    "                    return False\n",
    "                i -= 1\n",
    "                j -= 1\n",
    "            i = row - 1\n",
    "            j = col + 1 \n",
    "            while i >= 0 and j < len(board):\n",
    "                if board[i][j] == 'Q':\n",
    "                    return False\n",
    "                i -= 1\n",
    "                j += 1\n",
    "            return True\n",
    "\n",
    "        def backtracking(board, row, n):\n",
    "            if row == n:\n",
    "                temp_res = []\n",
    "                for temp in board:\n",
    "                    temp_str = ''.join(temp)\n",
    "                    temp_res.append(temp_str)\n",
    "                res.append(temp_res)\n",
    "            \n",
    "            for col in range(n):\n",
    "                if not is_Valid(board, row, col):\n",
    "                    continue\n",
    "                board[row][col] = 'Q'\n",
    "                backtracking(board, row+1, n)\n",
    "                board[row][col] = '.'\n",
    "        \n",
    "        backtracking(board, 0, n)\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def totalNQueens(self, n: int) -> List[List[str]]:\n",
    "        def setboard(range_K):\n",
    "            global chessboard\n",
    "            chessboard=[]\n",
    "            line=[0]*range_K\n",
    "            for i in range(range_K):\n",
    "                chessboard.append(copy.deepcopy(line))\n",
    "\n",
    "        def reset(range_K):\n",
    "            global chessboard\n",
    "            setboard(range_K)\n",
    "\n",
    "        def reset_on_answers(answers,range_K):\n",
    "            global chessboard\n",
    "            reset(range_K)\n",
    "            for answer in answers:\n",
    "                chessin(answer[0],answer[1],range_K)\n",
    "\n",
    "        def chessin(row_now,column_now,range_K):\n",
    "            global chessboard\n",
    "            for row in range(range_K):\n",
    "                for column in range(range_K):\n",
    "                    if row==row_now and column==column_now:\n",
    "                        chessboard[row][column]=3\n",
    "                    elif row==row_now or column==column_now or abs(row-row_now)==abs(column-column_now):    \n",
    "                        chessboard[row][column]=1\n",
    "\n",
    "        def debug():\n",
    "            global chessboard\n",
    "            print('分隔符')\n",
    "            for i in chessboard:\n",
    "                print(i)\n",
    "\n",
    "\n",
    "        def main(range_K):\n",
    "            if range_K==1:\n",
    "                return 1\n",
    "            global chessboard\n",
    "            group_of_result=[]\n",
    "            setboard(range_K)\n",
    "            reset(range_K)\n",
    "            answers=[]\n",
    "            number_of_answers=0\n",
    "            row=0\n",
    "            column=0\n",
    "            while row < (range_K+1):\n",
    "                if row <= (range_K-1):\n",
    "                    while column <= (range_K-1):\n",
    "                        if column <= (range_K-1):\n",
    "                            if chessboard[row][column]==0:\n",
    "                                chessin(row,column,range_K)\n",
    "                                answers.append([row,column])\n",
    "                                break\n",
    "                            else:\n",
    "                                column +=1\n",
    "                    if len(answers)==row+1:\n",
    "                        row +=1\n",
    "                        column=0\n",
    "                    else:\n",
    "                        if answers:\n",
    "                            false_answer=answers.pop()\n",
    "                            row=false_answer[0]\n",
    "                            column=false_answer[1]+1\n",
    "                            reset_on_answers(answers,range_K)\n",
    "                        else:\n",
    "                            break\n",
    "                else:\n",
    "                    result=copy.deepcopy(chessboard)\n",
    "                    for a in range(range_K):\n",
    "                        for b in range(range_K):\n",
    "                            if result[a][b]==3:\n",
    "                                result[a][b]='Q'\n",
    "                            else:\n",
    "                                result[a][b]='.'\n",
    "                    for a in range(range_K):\n",
    "                        result[a]=''.join(result[a])\n",
    "                    group_of_result.append(copy.deepcopy(result))\n",
    "                    number_of_answers +=1\n",
    "                    answers.pop()\n",
    "                    false_answer=answers.pop()\n",
    "                    reset_on_answers(answers,range_K)\n",
    "                    row=false_answer[0]\n",
    "                    column=false_answer[1]+1\n",
    "            return number_of_answers\n",
    "        return(main(n))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalNQueens(self, n: int) -> int:\n",
    "        m = n * 2 - 1\n",
    "        ans = 0\n",
    "        on_path, diag1, diag2 = [False] * n, [False] * m, [False] * m\n",
    "        def dfs(r: int) -> None:\n",
    "            if r == n:\n",
    "                nonlocal ans\n",
    "                ans += 1\n",
    "                return\n",
    "            for c, on in enumerate(on_path):\n",
    "                if not on and not diag1[r + c] and not diag2[r - c]:\n",
    "                    on_path[c] = diag1[r + c] = diag2[r - c] = True\n",
    "                    dfs(r + 1)\n",
    "                    on_path[c] = diag1[r + c] = diag2[r - c] = False  # 恢复现场\n",
    "        dfs(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalNQueens(self, n: int) -> int:\n",
    "        m=n*2-1\n",
    "        ans=0\n",
    "        col=[0]*n\n",
    "        on_path,diag1,diag2=[False]*n,[False]*m,[False]*m\n",
    "        def dfs(r):\n",
    "            if r==n:\n",
    "                nonlocal ans\n",
    "                ans+=1\n",
    "                return\n",
    "            for c, on in enumerate(on_path):\n",
    "                if not on and not diag1[r+c] and not diag2[r-c]:\n",
    "                    col[r]=c\n",
    "                    on_path[c]=diag1[r+c]=diag2[r-c]=True\n",
    "                    dfs(r+1)\n",
    "                    on_path[c]=diag1[r+c]=diag2[r-c]=False  # 恢复现场   \n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalNQueens(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        cnt, q = 0, [None] * n   # cnt 用计数，q用于已经放的位置，例如q[2]=3 表示第3行的放到了第4个位置\n",
    "\n",
    "        def dfs(k, n):\n",
    "            nonlocal cnt  # 使用外部变量\n",
    "            if k == n:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                for j in range(n):  # 一行一行的进行深度搜索\n",
    "                    if self.place(k, j, q):\n",
    "                        q[k] = j\n",
    "                        dfs(k+1, n)\n",
    "        dfs(0, n)\n",
    "        return cnt\n",
    "\n",
    "    def place(self, k, j, q):  # 判断该位置是否可以放一个棋子\n",
    "        for i in range(k):\n",
    "            if q[i] == j or abs(q[i]-j) == abs(i-k):  # 不同列，不同斜线\n",
    "                return 0\n",
    "        return 1\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    solu = Solution()\n",
    "    print(solu.totalNQueens(4))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalNQueens(self, n: int) -> int:\n",
    "        self.count = 0\n",
    "        board = [[\".\" for _ in range(n)] for _ in range(n)]\n",
    "        self.place_queens(n, 0, board)\n",
    "        return self.count\n",
    "\n",
    "    def place_queens(self, n, row, board):\n",
    "        if row == n:\n",
    "            self.count += 1\n",
    "            return\n",
    "\n",
    "        for col in range(n):\n",
    "            if self.is_safe(row, col, board, n):\n",
    "                board[row][col] = \"Q\"\n",
    "                self.place_queens(n, row + 1, board)\n",
    "                board[row][col] = \".\"\n",
    "\n",
    "    def is_safe(self, row, col, board, n):\n",
    "        for i in range(row):\n",
    "            if board[i][col] == \"Q\":\n",
    "                return False\n",
    "\n",
    "        i, j = row - 1, col - 1\n",
    "        while i >= 0 and j >= 0:\n",
    "            if board[i][j] == \"Q\":\n",
    "                return False\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "\n",
    "        i, j = row - 1, col + 1\n",
    "        while i >= 0 and j < n:\n",
    "            if board[i][j] == \"Q\":\n",
    "                return False\n",
    "            i -= 1\n",
    "            j += 1\n",
    "\n",
    "        return True\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
